// m

// 给定一个整体数组nums，要求找出数组中乘积最大的连续子数组（最少包含一个数字），并返回该子数组对应的乘积

// 解题思路：
// 乘积有个特殊情况，两个正数，两个负数相乘都会得到正数，所以求解的时候需要考虑负数的情况
// 若想最终的乘积最大，则应该使子数组中的正数元素尽可能的大，负数元素尽可能的小，所以可以维护一个最大值变量和最小值变量
// 动态规划的状态可以dpmax[i]表示 第i个元素结尾的乘积最大子数组的乘积，dpmin[i] 表示以第i个元素结尾的乘积最小数组的乘积

// 动态规划的状态转移方程可以写成
// dpmax[i] = max(dpmax[i-1] * nums[i], nums[i], dpmin[i-1] * nums[i])
// dpmin[i] = min(dpmin[i-1] * nums[i], nums[i], dpmax[i-1] * nums[i])
// 最后找出dpmax中最大值即为乘积最大子数组的乘积
// 因为状态转义方程中只涉及当前元素和前一个元素，所以我们可以不使用数组，只使用两个变量来维护dpmax[i]和dpmin[i]

function maxProduct(nums) {
    let size = nums.length
    let dp_max = new Array(size).fill(0)
    let dp_min = new Array(size).fill(0)
    dp_max[0] = nums[0]
    dp_min[0] = nums[0]
    for (let i = 1; i < size; i++) {
        dp_max[i] = Math.max(dp_max[i-1] * nums[i], nums[i], dp_min[i-1] * nums[i])        
        dp_min[i] = Math.min(dp_min[i-1] * nums[i], nums[i], dp_max[i-1] * nums[i])        
    }
    return Math.max(...dp_max)
}

function maxProduct(nums) {
    let size = nums.length
    let max_num = nums[0]
    let min_num = nums[0]
    let ans = nums[0]
    for (let i = 1; i < size; i++) {
        let temp_max = max_num
        let temp_min = min_num
        max_num = Math.max(temp_max * nums[i], nums[i], temp_min * nums[i])
        min_num = Math.min(temp_min * nums[i], nums[i], temp_max * nums[i])
        ans = Math.max(max_num, ans)
    }
    return ans
}

let nums = [-2, 0, -1, 3, 4]
console.log(maxProduct(nums));